
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <assert.h>
#include <immintrin.h>

#include <cstdint>
#include <cstddef>
#include <cstdbool>
#include <vector>
#include <algorithm>
#include <type_traits>

static const std::uint32_t kMaxDivTable = 512;

struct DivRatio32 {
    uint32_t mul;
    uint32_t add;
    uint32_t shift;
    uint32_t reserve;
};

static const DivRatio32 div_ratio_tbl32[kMaxDivTable] = {
    { 0x00000000, 0x00000000,  0, 0 }, { 0xFFFFFFFF, 0xFFFFFFFF,  0, 0 },
    { 0x80000000, 0x00000000,  0, 0 }, { 0xAAAAAAAB, 0x00000000,  1, 0 },
    { 0x40000000, 0x00000000,  0, 0 }, { 0xCCCCCCCD, 0x00000000,  2, 0 },
    { 0xAAAAAAAB, 0x00000000,  2, 0 }, { 0x92492492, 0x69F3E260,  2, 0 },
    { 0x20000000, 0x00000000,  0, 0 }, { 0xE38E38E4, 0x00000000,  3, 0 },
    { 0xCCCCCCCD, 0x00000000,  3, 0 }, { 0xBA2E8BA3, 0x00000000,  3, 0 },
    { 0xAAAAAAAB, 0x00000000,  3, 0 }, { 0x9D89D89E, 0x00000000,  3, 0 },
    { 0x92492492, 0x69F3E260,  3, 0 }, { 0x88888889, 0x00000000,  3, 0 },
    { 0x10000000, 0x00000000,  0, 0 }, { 0xF0F0F0F1, 0x00000000,  4, 0 },
    { 0xE38E38E4, 0x00000000,  4, 0 }, { 0xD79435E5, 0xCE637607,  4, 0 },
    { 0xCCCCCCCD, 0x00000000,  4, 0 }, { 0xC30C30C3, 0xBBB5CC50,  4, 0 },
    { 0xBA2E8BA3, 0x00000000,  4, 0 }, { 0xB21642C9, 0x00000000,  4, 0 },
    { 0xAAAAAAAB, 0x00000000,  4, 0 }, { 0xA3D70A3E, 0x00000000,  4, 0 },
    { 0x9D89D89E, 0x00000000,  4, 0 }, { 0x97B425ED, 0x939A23A6,  4, 0 },
    { 0x92492492, 0x69F3E260,  4, 0 }, { 0x8D3DCB09, 0x00000000,  4, 0 },
    { 0x88888889, 0x00000000,  4, 0 }, { 0x84210842, 0x7CED0647,  4, 0 },
    { 0x08000000, 0x00000000,  0, 0 }, { 0xF83E0F84, 0x00000000,  5, 0 },
    { 0xF0F0F0F1, 0x00000000,  5, 0 }, { 0xEA0EA0EA, 0xDF05E68C,  5, 0 },
    { 0xE38E38E4, 0x00000000,  5, 0 }, { 0xDD67C8A6, 0xD3A6CC3F,  5, 0 },
    { 0xD79435E5, 0xCE637607,  5, 0 }, { 0xD20D20D2, 0xC961450E,  5, 0 },
    { 0xCCCCCCCD, 0x00000000,  5, 0 }, { 0xC7CE0C7D, 0x00000000,  5, 0 },
    { 0xC30C30C3, 0xBBB5CC50,  5, 0 }, { 0xBE82FA0C, 0x00000000,  5, 0 },
    { 0xBA2E8BA3, 0x00000000,  5, 0 }, { 0xB60B60B6, 0xAFC62517,  5, 0 },
    { 0xB21642C9, 0x00000000,  5, 0 }, { 0xAE4C415D, 0x00000000,  5, 0 },
    { 0xAAAAAAAB, 0x00000000,  5, 0 }, { 0xA72F053A, 0x00000000,  5, 0 },
    { 0xA3D70A3E, 0x00000000,  5, 0 }, { 0xA0A0A0A1, 0x00000000,  5, 0 },
    { 0x9D89D89E, 0x00000000,  5, 0 }, { 0x9A90E7D9, 0x64B384ED,  5, 0 },
    { 0x97B425ED, 0x939A23A6,  5, 0 }, { 0x94F2094F, 0x837A6D79,  5, 0 },
    { 0x92492492, 0x69F3E260,  5, 0 }, { 0x8FB823EE, 0x8C1D1D48,  5, 0 },
    { 0x8D3DCB09, 0x00000000,  5, 0 }, { 0x8AD8F2FC, 0x00000000,  5, 0 },
    { 0x88888889, 0x00000000,  5, 0 }, { 0x864B8A7E, 0x00000000,  5, 0 },
    { 0x84210842, 0x7CED0647,  5, 0 }, { 0x82082082, 0x7F343F11,  5, 0 },
    { 0x04000000, 0x00000000,  0, 0 }, { 0xFC0FC0FD, 0x00000000,  6, 0 },
    { 0xF83E0F84, 0x00000000,  6, 0 }, { 0xF4898D60, 0x00000000,  6, 0 },
    { 0xF0F0F0F1, 0x00000000,  6, 0 }, { 0xED7303B6, 0x00000000,  6, 0 },
    { 0xEA0EA0EA, 0xDF05E68C,  6, 0 }, { 0xE6C2B449, 0x00000000,  6, 0 },
    { 0xE38E38E4, 0x00000000,  6, 0 }, { 0xE070381C, 0xD66281E5,  6, 0 },
    { 0xDD67C8A6, 0xD3A6CC3F,  6, 0 }, { 0xDA740DA8, 0x00000000,  6, 0 },
    { 0xD79435E5, 0xCE637607,  6, 0 }, { 0xD4C77B04, 0x00000000,  6, 0 },
    { 0xD20D20D2, 0xC961450E,  6, 0 }, { 0xCF6474A9, 0x00000000,  6, 0 },
    { 0xCCCCCCCD, 0x00000000,  6, 0 }, { 0xCA4587E7, 0x00000000,  6, 0 },
    { 0xC7CE0C7D, 0x00000000,  6, 0 }, { 0xC565C87C, 0x00000000,  6, 0 },
    { 0xC30C30C3, 0xBBB5CC50,  6, 0 }, { 0xC0C0C0C1, 0x00000000,  6, 0 },
    { 0xBE82FA0C, 0x00000000,  6, 0 }, { 0xBC52640C, 0x00000000,  6, 0 },
    { 0xBA2E8BA3, 0x00000000,  6, 0 }, { 0xB81702E1, 0x00000000,  6, 0 },
    { 0xB60B60B6, 0xAFC62517,  6, 0 }, { 0xB40B40B4, 0xADEE2A4F,  6, 0 },
    { 0xB21642C9, 0x00000000,  6, 0 }, { 0xB02C0B03, 0x00000000,  6, 0 },
    { 0xAE4C415D, 0x00000000,  6, 0 }, { 0xAC769184, 0xA6ED1B0E,  6, 0 },
    { 0xAAAAAAAB, 0x00000000,  6, 0 }, { 0xA8E83F57, 0x9AECABA7,  6, 0 },
    { 0xA72F053A, 0x00000000,  6, 0 }, { 0xA57EB503, 0x00000000,  6, 0 },
    { 0xA3D70A3E, 0x00000000,  6, 0 }, { 0xA237C32B, 0x95628B82,  6, 0 },
    { 0xA0A0A0A1, 0x00000000,  6, 0 }, { 0x9F1165E7, 0x897E521E,  6, 0 },
    { 0x9D89D89E, 0x00000000,  6, 0 }, { 0x9C09C09C, 0x97A77520,  6, 0 },
    { 0x9A90E7D9, 0x64B384ED,  6, 0 }, { 0x991F1A51, 0x65B4457A,  6, 0 },
    { 0x97B425ED, 0x939A23A6,  6, 0 }, { 0x964FDA6C, 0x924C8AAA,  6, 0 },
    { 0x94F2094F, 0x837A6D79,  6, 0 }, { 0x939A85C4, 0x8FC2B64A,  6, 0 },
    { 0x92492492, 0x69F3E260,  6, 0 }, { 0x90FDBC09, 0x8975959D,  6, 0 },
    { 0x8FB823EE, 0x8C1D1D48,  6, 0 }, { 0x8E78356D, 0x84BE953D,  6, 0 },
    { 0x8D3DCB09, 0x00000000,  6, 0 }, { 0x8C08C08C, 0x88A5A200,  6, 0 },
    { 0x8AD8F2FC, 0x00000000,  6, 0 }, { 0x89AE408A, 0x00000000,  6, 0 },
    { 0x88888889, 0x00000000,  6, 0 }, { 0x8767AB5F, 0x6CC86386,  6, 0 },
    { 0x864B8A7E, 0x00000000,  6, 0 }, { 0x85340853, 0x64F6B528,  6, 0 },
    { 0x84210842, 0x7CED0647,  6, 0 }, { 0x83126E98, 0x00000000,  6, 0 },
    { 0x82082082, 0x7F343F11,  6, 0 }, { 0x81020408, 0x7A2BE5E0,  6, 0 },
    { 0x02000000, 0x00000000,  0, 0 }, { 0xFE03F810, 0x00000000,  7, 0 },
    { 0xFC0FC0FD, 0x00000000,  7, 0 }, { 0xFA232CF3, 0x00000000,  7, 0 },
    { 0xF83E0F84, 0x00000000,  7, 0 }, { 0xF6603D99, 0x00000000,  7, 0 },
    { 0xF4898D60, 0x00000000,  7, 0 }, { 0xF2B9D649, 0x00000000,  7, 0 },
    { 0xF0F0F0F1, 0x00000000,  7, 0 }, { 0xEF2EB720, 0x00000000,  7, 0 },
    { 0xED7303B6, 0x00000000,  7, 0 }, { 0xEBBDB2A6, 0x00000000,  7, 0 },
    { 0xEA0EA0EA, 0xDF05E68C,  7, 0 }, { 0xE865AC7C, 0x00000000,  7, 0 },
    { 0xE6C2B449, 0x00000000,  7, 0 }, { 0xE525982B, 0x00000000,  7, 0 },
    { 0xE38E38E4, 0x00000000,  7, 0 }, { 0xE1FC780F, 0x00000000,  7, 0 },
    { 0xE070381C, 0xD66281E5,  7, 0 }, { 0xDEE95C4D, 0x00000000,  7, 0 },
    { 0xDD67C8A6, 0xD3A6CC3F,  7, 0 }, { 0xDBEB61EF, 0x00000000,  7, 0 },
    { 0xDA740DA8, 0x00000000,  7, 0 }, { 0xD901B204, 0x00000000,  7, 0 },
    { 0xD79435E5, 0xCE637607,  7, 0 }, { 0xD62B80D7, 0x00000000,  7, 0 },
    { 0xD4C77B04, 0x00000000,  7, 0 }, { 0xD3680D37, 0x00000000,  7, 0 },
    { 0xD20D20D2, 0xC961450E,  7, 0 }, { 0xD0B69FCC, 0x00000000,  7, 0 },
    { 0xCF6474A9, 0x00000000,  7, 0 }, { 0xCE168A77, 0xB25660BB,  7, 0 },
    { 0xCCCCCCCD, 0x00000000,  7, 0 }, { 0xCB8727C1, 0x00000000,  7, 0 },
    { 0xCA4587E7, 0x00000000,  7, 0 }, { 0xC907DA4F, 0x00000000,  7, 0 },
    { 0xC7CE0C7D, 0x00000000,  7, 0 }, { 0xC6980C6A, 0x00000000,  7, 0 },
    { 0xC565C87C, 0x00000000,  7, 0 }, { 0xC4372F86, 0x00000000,  7, 0 },
    { 0xC30C30C3, 0xBBB5CC50,  7, 0 }, { 0xC1E4BBD6, 0x00000000,  7, 0 },
    { 0xC0C0C0C1, 0x00000000,  7, 0 }, { 0xBFA02FE8, 0xB893BB41,  7, 0 },
    { 0xBE82FA0C, 0x00000000,  7, 0 }, { 0xBD691047, 0xB9D48B37,  7, 0 },
    { 0xBC52640C, 0x00000000,  7, 0 }, { 0xBB3EE722, 0x00000000,  7, 0 },
    { 0xBA2E8BA3, 0x00000000,  7, 0 }, { 0xB92143FA, 0x933C5F93,  7, 0 },
    { 0xB81702E1, 0x00000000,  7, 0 }, { 0xB70FBB5A, 0xA67BCF7D,  7, 0 },
    { 0xB60B60B6, 0xAFC62517,  7, 0 }, { 0xB509E68B, 0x00000000,  7, 0 },
    { 0xB40B40B4, 0xADEE2A4F,  7, 0 }, { 0xB30F6353, 0x00000000,  7, 0 },
    { 0xB21642C9, 0x00000000,  7, 0 }, { 0xB11FD3B8, 0xAB3C7195,  7, 0 },
    { 0xB02C0B03, 0x00000000,  7, 0 }, { 0xAF3ADDC7, 0x00000000,  7, 0 },
    { 0xAE4C415D, 0x00000000,  7, 0 }, { 0xAD602B58, 0xA7C552BC,  7, 0 },
    { 0xAC769184, 0xA6ED1B0E,  7, 0 }, { 0xAB8F69E3, 0x00000000,  7, 0 },
    { 0xAAAAAAAB, 0x00000000,  7, 0 }, { 0xA9C84A48, 0x00000000,  7, 0 },
    { 0xA8E83F57, 0x9AECABA7,  7, 0 }, { 0xA80A80A8, 0xA2D3D378,  7, 0 },
    { 0xA72F053A, 0x00000000,  7, 0 }, { 0xA655C439, 0x8A724E13,  7, 0 },
    { 0xA57EB503, 0x00000000,  7, 0 }, { 0xA4A9CF1E, 0x00000000,  7, 0 },
    { 0xA3D70A3E, 0x00000000,  7, 0 }, { 0xA3065E40, 0x00000000,  7, 0 },
    { 0xA237C32B, 0x95628B82,  7, 0 }, { 0xA16B312F, 0x00000000,  7, 0 },
    { 0xA0A0A0A1, 0x00000000,  7, 0 }, { 0x9FD809FE, 0x00000000,  7, 0 },
    { 0x9F1165E7, 0x897E521E,  7, 0 }, { 0x9E4CAD24, 0x00000000,  7, 0 },
    { 0x9D89D89E, 0x00000000,  7, 0 }, { 0x9CC8E161, 0x00000000,  7, 0 },
    { 0x9C09C09C, 0x97A77520,  7, 0 }, { 0x9B4C6F9F, 0x00000000,  7, 0 },
    { 0x9A90E7D9, 0x64B384ED,  7, 0 }, { 0x99D722DB, 0x00000000,  7, 0 },
    { 0x991F1A51, 0x65B4457A,  7, 0 }, { 0x9868C80A, 0x00000000,  7, 0 },
    { 0x97B425ED, 0x939A23A6,  7, 0 }, { 0x97012E02, 0x623C8B4D,  7, 0 },
    { 0x964FDA6C, 0x924C8AAA,  7, 0 }, { 0x95A02568, 0x91A7F467,  7, 0 },
    { 0x94F2094F, 0x837A6D79,  7, 0 }, { 0x94458094, 0x6D7FDD57,  7, 0 },
    { 0x939A85C4, 0x8FC2B64A,  7, 0 }, { 0x92F11384, 0x91C680AA,  7, 0 },
    { 0x92492492, 0x69F3E260,  7, 0 }, { 0x91A2B3C5, 0x00000000,  7, 0 },
    { 0x90FDBC09, 0x8975959D,  7, 0 }, { 0x905A3863, 0x6ED216A5,  7, 0 },
    { 0x8FB823EE, 0x8C1D1D48,  7, 0 }, { 0x8F1779DA, 0x00000000,  7, 0 },
    { 0x8E78356D, 0x84BE953D,  7, 0 }, { 0x8DDA5202, 0x7091389C,  7, 0 },
    { 0x8D3DCB09, 0x00000000,  7, 0 }, { 0x8CA29C04, 0x56830362,  7, 0 },
    { 0x8C08C08C, 0x88A5A200,  7, 0 }, { 0x8B70344A, 0x8226FCD2,  7, 0 },
    { 0x8AD8F2FC, 0x00000000,  7, 0 }, { 0x8A42F870, 0x5CF941FA,  7, 0 },
    { 0x89AE408A, 0x00000000,  7, 0 }, { 0x891AC73B, 0x00000000,  7, 0 },
    { 0x88888889, 0x00000000,  7, 0 }, { 0x87F78088, 0x00000000,  7, 0 },
    { 0x8767AB5F, 0x6CC86386,  7, 0 }, { 0x86D90545, 0x00000000,  7, 0 },
    { 0x864B8A7E, 0x00000000,  7, 0 }, { 0x85BF3761, 0x6F9C450C,  7, 0 },
    { 0x85340853, 0x64F6B528,  7, 0 }, { 0x84A9F9C8, 0x81B19C96,  7, 0 },
    { 0x84210842, 0x7CED0647,  7, 0 }, { 0x83993052, 0x64259D62,  7, 0 },
    { 0x83126E98, 0x00000000,  7, 0 }, { 0x828CBFBF, 0x00000000,  7, 0 },
    { 0x82082082, 0x7F343F11,  7, 0 }, { 0x81848DA9, 0x00000000,  7, 0 },
    { 0x81020408, 0x7A2BE5E0,  7, 0 }, { 0x80808081, 0x00000000,  7, 0 },
    { 0x01000000, 0x00000000,  0, 0 }, { 0xFF00FF01, 0x00000000,  8, 0 },
    { 0xFE03F810, 0x00000000,  8, 0 }, { 0xFD08E551, 0x00000000,  8, 0 },
    { 0xFC0FC0FD, 0x00000000,  8, 0 }, { 0xFB188566, 0x00000000,  8, 0 },
    { 0xFA232CF3, 0x00000000,  8, 0 }, { 0xF92FB222, 0x00000000,  8, 0 },
    { 0xF83E0F84, 0x00000000,  8, 0 }, { 0xF74E3FC3, 0x00000000,  8, 0 },
    { 0xF6603D99, 0x00000000,  8, 0 }, { 0xF57403D6, 0x00000000,  8, 0 },
    { 0xF4898D60, 0x00000000,  8, 0 }, { 0xF3A0D52D, 0x00000000,  8, 0 },
    { 0xF2B9D649, 0x00000000,  8, 0 }, { 0xF1D48BCF, 0x00000000,  8, 0 },
    { 0xF0F0F0F1, 0x00000000,  8, 0 }, { 0xF00F00F0, 0xE463CBA3,  8, 0 },
    { 0xEF2EB720, 0x00000000,  8, 0 }, { 0xEE500EE5, 0xEE500EE5,  8, 0 },
    { 0xED7303B6, 0x00000000,  8, 0 }, { 0xEC979119, 0x00000000,  8, 0 },
    { 0xEBBDB2A6, 0x00000000,  8, 0 }, { 0xEAE56404, 0x00000000,  8, 0 },
    { 0xEA0EA0EA, 0xDF05E68C,  8, 0 }, { 0xE9396520, 0x00000000,  8, 0 },
    { 0xE865AC7C, 0x00000000,  8, 0 }, { 0xE79372E3, 0x00000000,  8, 0 },
    { 0xE6C2B449, 0x00000000,  8, 0 }, { 0xE5F36CB0, 0xDB5741B7,  8, 0 },
    { 0xE525982B, 0x00000000,  8, 0 }, { 0xE45932D8, 0x00000000,  8, 0 },
    { 0xE38E38E4, 0x00000000,  8, 0 }, { 0xE2C4A689, 0x00000000,  8, 0 },
    { 0xE1FC780F, 0x00000000,  8, 0 }, { 0xE135A9CA, 0x00000000,  8, 0 },
    { 0xE070381C, 0xD66281E5,  8, 0 }, { 0xDFAC1F75, 0x00000000,  8, 0 },
    { 0xDEE95C4D, 0x00000000,  8, 0 }, { 0xDE27EB2D, 0x00000000,  8, 0 },
    { 0xDD67C8A6, 0xD3A6CC3F,  8, 0 }, { 0xDCA8F159, 0x00000000,  8, 0 },
    { 0xDBEB61EF, 0x00000000,  8, 0 }, { 0xDB2F171E, 0x00000000,  8, 0 },
    { 0xDA740DA8, 0x00000000,  8, 0 }, { 0xD9BA4257, 0x00000000,  8, 0 },
    { 0xD901B204, 0x00000000,  8, 0 }, { 0xD84A598F, 0x00000000,  8, 0 },
    { 0xD79435E5, 0xCE637607,  8, 0 }, { 0xD6DF43FD, 0x00000000,  8, 0 },
    { 0xD62B80D7, 0x00000000,  8, 0 }, { 0xD578E97D, 0x00000000,  8, 0 },
    { 0xD4C77B04, 0x00000000,  8, 0 }, { 0xD417328A, 0x00000000,  8, 0 },
    { 0xD3680D37, 0x00000000,  8, 0 }, { 0xD2BA083C, 0x00000000,  8, 0 },
    { 0xD20D20D2, 0xC961450E,  8, 0 }, { 0xD161543E, 0xB206D66B,  8, 0 },
    { 0xD0B69FCC, 0x00000000,  8, 0 }, { 0xD00D00D0, 0xC7904AE6,  8, 0 },
    { 0xCF6474A9, 0x00000000,  8, 0 }, { 0xCEBCF8BC, 0x00000000,  8, 0 },
    { 0xCE168A77, 0xB25660BB,  8, 0 }, { 0xCD712753, 0x00000000,  8, 0 },
    { 0xCCCCCCCD, 0x00000000,  8, 0 }, { 0xCC29786D, 0x00000000,  8, 0 },
    { 0xCB8727C1, 0x00000000,  8, 0 }, { 0xCAE5D85F, 0xB6F0E137,  8, 0 },
    { 0xCA4587E7, 0x00000000,  8, 0 }, { 0xC9A633FD, 0x00000000,  8, 0 },
    { 0xC907DA4F, 0x00000000,  8, 0 }, { 0xC86A7890, 0xC09D2039,  8, 0 },
    { 0xC7CE0C7D, 0x00000000,  8, 0 }, { 0xC73293D8, 0x00000000,  8, 0 },
    { 0xC6980C6A, 0x00000000,  8, 0 }, { 0xC5FE7403, 0xB56E3F8B,  8, 0 },
    { 0xC565C87C, 0x00000000,  8, 0 }, { 0xC4CE07B0, 0xBD5117F4,  8, 0 },
    { 0xC4372F86, 0x00000000,  8, 0 }, { 0xC3A13DE6, 0xC215133A,  8, 0 },
    { 0xC30C30C3, 0xBBB5CC50,  8, 0 }, { 0xC2780614, 0x00000000,  8, 0 },
    { 0xC1E4BBD6, 0x00000000,  8, 0 }, { 0xC152500C, 0xB34985C9,  8, 0 },
    { 0xC0C0C0C1, 0x00000000,  8, 0 }, { 0xC0300C03, 0xC0300C03,  8, 0 },
    { 0xBFA02FE8, 0xB893BB41,  8, 0 }, { 0xBF112A8B, 0x00000000,  8, 0 },
    { 0xBE82FA0C, 0x00000000,  8, 0 }, { 0xBDF59C92, 0x00000000,  8, 0 },
    { 0xBD691047, 0xB9D48B37,  8, 0 }, { 0xBCDD535E, 0x00000000,  8, 0 },
    { 0xBC52640C, 0x00000000,  8, 0 }, { 0xBBC8408D, 0x00000000,  8, 0 },
    { 0xBB3EE722, 0x00000000,  8, 0 }, { 0xBAB65610, 0xB4117875,  8, 0 },
    { 0xBA2E8BA3, 0x00000000,  8, 0 }, { 0xB9A7862A, 0xAFF0BCAC,  8, 0 },
    { 0xB92143FA, 0x933C5F93,  8, 0 }, { 0xB89BC36D, 0x00000000,  8, 0 },
    { 0xB81702E1, 0x00000000,  8, 0 }, { 0xB79300B8, 0x00000000,  8, 0 },
    { 0xB70FBB5A, 0xA67BCF7D,  8, 0 }, { 0xB68D3134, 0xAE3500D4,  8, 0 },
    { 0xB60B60B6, 0xAFC62517,  8, 0 }, { 0xB58A4855, 0xA5C1354C,  8, 0 },
    { 0xB509E68B, 0x00000000,  8, 0 }, { 0xB48A39D4, 0x849C1C52,  8, 0 },
    { 0xB40B40B4, 0xADEE2A4F,  8, 0 }, { 0xB38CF9B0, 0xAD79B893,  8, 0 },
    { 0xB30F6353, 0x00000000,  8, 0 }, { 0xB2927C2A, 0x00000000,  8, 0 },
    { 0xB21642C9, 0x00000000,  8, 0 }, { 0xB19AB5C5, 0x00000000,  8, 0 },
    { 0xB11FD3B8, 0xAB3C7195,  8, 0 }, { 0xB0A59B42, 0x00000000,  8, 0 },
    { 0xB02C0B03, 0x00000000,  8, 0 }, { 0xAFB321A1, 0x7F0E0F35,  8, 0 },
    { 0xAF3ADDC7, 0x00000000,  8, 0 }, { 0xAEC33E20, 0x00000000,  8, 0 },
    { 0xAE4C415D, 0x00000000,  8, 0 }, { 0xADD5E632, 0x843AF5EC,  8, 0 },
    { 0xAD602B58, 0xA7C552BC,  8, 0 }, { 0xACEB0F89, 0x9A1DC09D,  8, 0 },
    { 0xAC769184, 0xA6ED1B0E,  8, 0 }, { 0xAC02B00B, 0x00000000,  8, 0 },
    { 0xAB8F69E3, 0x00000000,  8, 0 }, { 0xAB1CBDD4, 0x00000000,  8, 0 },
    { 0xAAAAAAAB, 0x00000000,  8, 0 }, { 0xAA392F36, 0x00000000,  8, 0 },
    { 0xA9C84A48, 0x00000000,  8, 0 }, { 0xA957FAB5, 0x80977E74,  8, 0 },
    { 0xA8E83F57, 0x9AECABA7,  8, 0 }, { 0xA8791709, 0x00000000,  8, 0 },
    { 0xA80A80A8, 0xA2D3D378,  8, 0 }, { 0xA79C7B17, 0x00000000,  8, 0 },
    { 0xA72F053A, 0x00000000,  8, 0 }, { 0xA6C21DF7, 0x00000000,  8, 0 },
    { 0xA655C439, 0x8A724E13,  8, 0 }, { 0xA5E9F6ED, 0x858CD9DD,  8, 0 },
    { 0xA57EB503, 0x00000000,  8, 0 }, { 0xA513FD6C, 0x00000000,  8, 0 },
    { 0xA4A9CF1E, 0x00000000,  8, 0 }, { 0xA4402910, 0x9F4E81B5,  8, 0 },
    { 0xA3D70A3E, 0x00000000,  8, 0 }, { 0xA36E71A3, 0x00000000,  8, 0 },
    { 0xA3065E40, 0x00000000,  8, 0 }, { 0xA29ECF16, 0x7E50B482,  8, 0 },
    { 0xA237C32B, 0x95628B82,  8, 0 }, { 0xA1D13986, 0x00000000,  8, 0 },
    { 0xA16B312F, 0x00000000,  8, 0 }, { 0xA105A933, 0x00000000,  8, 0 },
    { 0xA0A0A0A1, 0x00000000,  8, 0 }, { 0xA03C1689, 0x00000000,  8, 0 },
    { 0x9FD809FE, 0x00000000,  8, 0 }, { 0x9F747A15, 0x84BA5390,  8, 0 },
    { 0x9F1165E7, 0x897E521E,  8, 0 }, { 0x9EAECC8D, 0x6C666209,  8, 0 },
    { 0x9E4CAD24, 0x00000000,  8, 0 }, { 0x9DEB06C9, 0x8FE54ABD,  8, 0 },
    { 0x9D89D89E, 0x00000000,  8, 0 }, { 0x9D2921C4, 0x00000000,  8, 0 },
    { 0x9CC8E161, 0x00000000,  8, 0 }, { 0x9C69169B, 0x807BFB36,  8, 0 },
    { 0x9C09C09C, 0x97A77520,  8, 0 }, { 0x9BAADE8E, 0x701D23F9,  8, 0 },
    { 0x9B4C6F9F, 0x00000000,  8, 0 }, { 0x9AEE72FD, 0x00000000,  8, 0 },
    { 0x9A90E7D9, 0x64B384ED,  8, 0 }, { 0x9A33CD67, 0x9A33CD67,  8, 0 },
    { 0x99D722DB, 0x00000000,  8, 0 }, { 0x997AE76B, 0x6A7DA15E,  8, 0 },
    { 0x991F1A51, 0x65B4457A,  8, 0 }, { 0x98C3BAC7, 0x6AEE7FCC,  8, 0 },
    { 0x9868C80A, 0x00000000,  8, 0 }, { 0x980E4156, 0x86867353,  8, 0 },
    { 0x97B425ED, 0x939A23A6,  8, 0 }, { 0x975A7510, 0x00000000,  8, 0 },
    { 0x97012E02, 0x623C8B4D,  8, 0 }, { 0x96A8500A, 0x00000000,  8, 0 },
    { 0x964FDA6C, 0x924C8AAA,  8, 0 }, { 0x95F7CC73, 0x00000000,  8, 0 },
    { 0x95A02568, 0x91A7F467,  8, 0 }, { 0x9548E498, 0x00000000,  8, 0 },
    { 0x94F2094F, 0x837A6D79,  8, 0 }, { 0x949B92DE, 0x00000000,  8, 0 },
    { 0x94458094, 0x6D7FDD57,  8, 0 }, { 0x93EFD1C5, 0x8D114F43,  8, 0 },
    { 0x939A85C4, 0x8FC2B64A,  8, 0 }, { 0x93459BE7, 0x00000000,  8, 0 },
    { 0x92F11384, 0x91C680AA,  8, 0 }, { 0x929CEBF5, 0x00000000,  8, 0 },
    { 0x92492492, 0x69F3E260,  8, 0 }, { 0x91F5BCB9, 0x00000000,  8, 0 },
    { 0x91A2B3C5, 0x00000000,  8, 0 }, { 0x91500915, 0x91500915,  8, 0 },
    { 0x90FDBC09, 0x8975959D,  8, 0 }, { 0x90ABCC02, 0x6C6EDC7D,  8, 0 },
    { 0x905A3863, 0x6ED216A5,  8, 0 }, { 0x90090090, 0x8C691969,  8, 0 },
    { 0x8FB823EE, 0x8C1D1D48,  8, 0 }, { 0x8F67A1E4, 0x00000000,  8, 0 },
    { 0x8F1779DA, 0x00000000,  8, 0 }, { 0x8EC7AB3A, 0x00000000,  8, 0 },
    { 0x8E78356D, 0x84BE953D,  8, 0 }, { 0x8E2917E1, 0x00000000,  8, 0 },
    { 0x8DDA5202, 0x7091389C,  8, 0 }, { 0x8D8BE340, 0x00000000,  8, 0 },
    { 0x8D3DCB09, 0x00000000,  8, 0 }, { 0x8CF008CF, 0x8CF008CF,  8, 0 },
    { 0x8CA29C04, 0x56830362,  8, 0 }, { 0x8C55841D, 0x00000000,  8, 0 },
    { 0x8C08C08C, 0x88A5A200,  8, 0 }, { 0x8BBC50C9, 0x00000000,  8, 0 },
    { 0x8B70344A, 0x8226FCD2,  8, 0 }, { 0x8B246A88, 0x00000000,  8, 0 },
    { 0x8AD8F2FC, 0x00000000,  8, 0 }, { 0x8A8DCD20, 0x00000000,  8, 0 },
    { 0x8A42F870, 0x5CF941FA,  8, 0 }, { 0x89F8746A, 0x00000000,  8, 0 },
    { 0x89AE408A, 0x00000000,  8, 0 }, { 0x89645C4F, 0x4FB81368,  8, 0 },
    { 0x891AC73B, 0x00000000,  8, 0 }, { 0x88D180CD, 0x6B0D740F,  8, 0 },
    { 0x88888889, 0x00000000,  8, 0 }, { 0x883FDDF0, 0x85146A88,  8, 0 },
    { 0x87F78088, 0x00000000,  8, 0 }, { 0x87AF6FD6, 0x00000000,  8, 0 },
    { 0x8767AB5F, 0x6CC86386,  8, 0 }, { 0x872032AC, 0x7E727327,  8, 0 },
    { 0x86D90545, 0x00000000,  8, 0 }, { 0x869222B2, 0x00000000,  8, 0 },
    { 0x864B8A7E, 0x00000000,  8, 0 }, { 0x86053C34, 0x58387342,  8, 0 },
    { 0x85BF3761, 0x6F9C450C,  8, 0 }, { 0x85797B91, 0x488EB47B,  8, 0 },
    { 0x85340853, 0x64F6B528,  8, 0 }, { 0x84EEDD36, 0x00000000,  8, 0 },
    { 0x84A9F9C8, 0x81B19C96,  8, 0 }, { 0x84655D9C, 0x00000000,  8, 0 },
    { 0x84210842, 0x7CED0647,  8, 0 }, { 0x83DCF94E, 0x00000000,  8, 0 },
    { 0x83993052, 0x64259D62,  8, 0 }, { 0x8355ACE4, 0x00000000,  8, 0 },
    { 0x83126E98, 0x00000000,  8, 0 }, { 0x82CF7504, 0x00000000,  8, 0 },
    { 0x828CBFBF, 0x00000000,  8, 0 }, { 0x824A4E61, 0x00000000,  8, 0 },
    { 0x82082082, 0x7F343F11,  8, 0 }, { 0x81C635BC, 0x79D21D7C,  8, 0 },
    { 0x81848DA9, 0x00000000,  8, 0 }, { 0x814327E4, 0x00000000,  8, 0 },
    { 0x81020408, 0x7A2BE5E0,  8, 0 }, { 0x80C121B3, 0x00000000,  8, 0 },
    { 0x80808081, 0x00000000,  8, 0 }, { 0x80402010, 0x7D84704D,  8, 0 },
};

static const DivRatio32 div_ratio_tbl32_64[kMaxDivTable] = {
    { 0x00000000, 0x00000000, 32, 0 }, { 0xFFFFFFFF, 0xFFFFFFFF, 32, 0 },
    { 0x80000000, 0x00000000, 32, 0 }, { 0xAAAAAAAB, 0x00000000, 33, 0 },
    { 0x40000000, 0x00000000, 32, 0 }, { 0xCCCCCCCD, 0x00000000, 34, 0 },
    { 0xAAAAAAAB, 0x00000000, 34, 0 }, { 0x92492492, 0x6938A379, 34, 0 },
    { 0x20000000, 0x00000000, 32, 0 }, { 0xE38E38E4, 0x00000000, 35, 0 },
    { 0xCCCCCCCD, 0x00000000, 35, 0 }, { 0xBA2E8BA3, 0x00000000, 35, 0 },
    { 0xAAAAAAAB, 0x00000000, 35, 0 }, { 0x9D89D89E, 0x00000000, 35, 0 },
    { 0x92492492, 0x6938A379, 35, 0 }, { 0x88888889, 0x00000000, 35, 0 },
    { 0x10000000, 0x00000000, 32, 0 }, { 0xF0F0F0F1, 0x00000000, 36, 0 },
    { 0xE38E38E4, 0x00000000, 36, 0 }, { 0xD79435E5, 0xCD4F851E, 36, 0 },
    { 0xCCCCCCCD, 0x00000000, 36, 0 }, { 0xC30C30C3, 0xBABC231B, 36, 0 },
    { 0xBA2E8BA3, 0x00000000, 36, 0 }, { 0xB21642C9, 0x00000000, 36, 0 },
    { 0xAAAAAAAB, 0x00000000, 36, 0 }, { 0xA3D70A3E, 0x00000000, 36, 0 },
    { 0x9D89D89E, 0x00000000, 36, 0 }, { 0x97B425ED, 0x92D7F561, 36, 0 },
    { 0x92492492, 0x6938A379, 36, 0 }, { 0x8D3DCB09, 0x00000000, 36, 0 },
    { 0x88888889, 0x00000000, 36, 0 }, { 0x84210842, 0x7C43E63C, 36, 0 },
    { 0x08000000, 0x00000000, 32, 0 }, { 0xF83E0F84, 0x00000000, 37, 0 },
    { 0xF0F0F0F1, 0x00000000, 37, 0 }, { 0xEA0EA0EA, 0xDDDA4EB3, 37, 0 },
    { 0xE38E38E4, 0x00000000, 37, 0 }, { 0xDD67C8A6, 0xD28B661F, 37, 0 },
    { 0xD79435E5, 0xCD4F851E, 37, 0 }, { 0xD20D20D2, 0xC8546773, 37, 0 },
    { 0xCCCCCCCD, 0x00000000, 37, 0 }, { 0xC7CE0C7D, 0x00000000, 37, 0 },
    { 0xC30C30C3, 0xBABC231B, 37, 0 }, { 0xBE82FA0C, 0x00000000, 37, 0 },
    { 0xBA2E8BA3, 0x00000000, 37, 0 }, { 0xB60B60B6, 0xAEDD20C4, 37, 0 },
    { 0xB21642C9, 0x00000000, 37, 0 }, { 0xAE4C415D, 0x00000000, 37, 0 },
    { 0xAAAAAAAB, 0x00000000, 37, 0 }, { 0xA72F053A, 0x00000000, 37, 0 },
    { 0xA3D70A3E, 0x00000000, 37, 0 }, { 0xA0A0A0A1, 0x00000000, 37, 0 },
    { 0x9D89D89E, 0x00000000, 37, 0 }, { 0x9A90E7D9, 0x63EDACBA, 37, 0 },
    { 0x97B425ED, 0x92D7F561, 37, 0 }, { 0x94F2094F, 0x82BBC707, 37, 0 },
    { 0x92492492, 0x6938A379, 37, 0 }, { 0x8FB823EE, 0x8B652757, 37, 0 },
    { 0x8D3DCB09, 0x00000000, 37, 0 }, { 0x8AD8F2FC, 0x00000000, 37, 0 },
    { 0x88888889, 0x00000000, 37, 0 }, { 0x864B8A7E, 0x00000000, 37, 0 },
    { 0x84210842, 0x7C43E63C, 37, 0 }, { 0x82082082, 0x7E8DCE43, 37, 0 },
    { 0x04000000, 0x00000000, 32, 0 }, { 0xFC0FC0FD, 0x00000000, 38, 0 },
    { 0xF83E0F84, 0x00000000, 38, 0 }, { 0xF4898D60, 0x00000000, 38, 0 },
    { 0xF0F0F0F1, 0x00000000, 38, 0 }, { 0xED7303B6, 0x00000000, 38, 0 },
    { 0xEA0EA0EA, 0xDDDA4EB3, 38, 0 }, { 0xE6C2B449, 0x00000000, 38, 0 },
    { 0xE38E38E4, 0x00000000, 38, 0 }, { 0xE070381C, 0xD54339EE, 38, 0 },
    { 0xDD67C8A6, 0xD28B661F, 38, 0 }, { 0xDA740DA8, 0x00000000, 38, 0 },
    { 0xD79435E5, 0xCD4F851E, 38, 0 }, { 0xD4C77B04, 0x00000000, 38, 0 },
    { 0xD20D20D2, 0xC8546773, 38, 0 }, { 0xCF6474A9, 0x00000000, 38, 0 },
    { 0xCCCCCCCD, 0x00000000, 38, 0 }, { 0xCA4587E7, 0x00000000, 38, 0 },
    { 0xC7CE0C7D, 0x00000000, 38, 0 }, { 0xC565C87C, 0x00000000, 38, 0 },
    { 0xC30C30C3, 0xBABC231B, 38, 0 }, { 0xC0C0C0C1, 0x00000000, 38, 0 },
    { 0xBE82FA0C, 0x00000000, 38, 0 }, { 0xBC52640C, 0x00000000, 38, 0 },
    { 0xBA2E8BA3, 0x00000000, 38, 0 }, { 0xB81702E1, 0x00000000, 38, 0 },
    { 0xB60B60B6, 0xAEDD20C4, 38, 0 }, { 0xB40B40B4, 0xAD07B581, 38, 0 },
    { 0xB21642C9, 0x00000000, 38, 0 }, { 0xB02C0B03, 0x00000000, 38, 0 },
    { 0xAE4C415D, 0x00000000, 38, 0 }, { 0xAC769184, 0xA6105A53, 38, 0 },
    { 0xAAAAAAAB, 0x00000000, 38, 0 }, { 0xA8E83F57, 0x9A147822, 38, 0 },
    { 0xA72F053A, 0x00000000, 38, 0 }, { 0xA57EB503, 0x00000000, 38, 0 },
    { 0xA3D70A3E, 0x00000000, 38, 0 }, { 0xA237C32B, 0x9492E7F8, 38, 0 },
    { 0xA0A0A0A1, 0x00000000, 38, 0 }, { 0x9F1165E7, 0x88B2B6BA, 38, 0 },
    { 0x9D89D89E, 0x00000000, 38, 0 }, { 0x9C09C09C, 0x96DFBA90, 38, 0 },
    { 0x9A90E7D9, 0x63EDACBA, 38, 0 }, { 0x991F1A51, 0x64F046A0, 38, 0 },
    { 0x97B425ED, 0x92D7F561, 38, 0 }, { 0x964FDA6C, 0x918C2473, 38, 0 },
    { 0x94F2094F, 0x82BBC707, 38, 0 }, { 0x939A85C4, 0x8F05C78A, 38, 0 },
    { 0x92492492, 0x6938A379, 38, 0 }, { 0x90FDBC09, 0x88BBFEE9, 38, 0 },
    { 0x8FB823EE, 0x8B652757, 38, 0 }, { 0x8E78356D, 0x840838CF, 38, 0 },
    { 0x8D3DCB09, 0x00000000, 38, 0 }, { 0x8C08C08C, 0x87F26399, 38, 0 },
    { 0x8AD8F2FC, 0x00000000, 38, 0 }, { 0x89AE408A, 0x00000000, 38, 0 },
    { 0x88888889, 0x00000000, 38, 0 }, { 0x8767AB5F, 0x6C1B1206, 38, 0 },
    { 0x864B8A7E, 0x00000000, 38, 0 }, { 0x85340853, 0x644C351D, 38, 0 },
    { 0x84210842, 0x7C43E63C, 38, 0 }, { 0x83126E98, 0x00000000, 38, 0 },
    { 0x82082082, 0x7E8DCE43, 38, 0 }, { 0x81020408, 0x7986C493, 38, 0 },
    { 0x02000000, 0x00000000, 32, 0 }, { 0xFE03F810, 0x00000000, 39, 0 },
    { 0xFC0FC0FD, 0x00000000, 39, 0 }, { 0xFA232CF3, 0x00000000, 39, 0 },
    { 0xF83E0F84, 0x00000000, 39, 0 }, { 0xF6603D99, 0x00000000, 39, 0 },
    { 0xF4898D60, 0x00000000, 39, 0 }, { 0xF2B9D649, 0x00000000, 39, 0 },
    { 0xF0F0F0F1, 0x00000000, 39, 0 }, { 0xEF2EB720, 0x00000000, 39, 0 },
    { 0xED7303B6, 0x00000000, 39, 0 }, { 0xEBBDB2A6, 0x00000000, 39, 0 },
    { 0xEA0EA0EA, 0xDDDA4EB3, 39, 0 }, { 0xE865AC7C, 0x00000000, 39, 0 },
    { 0xE6C2B449, 0x00000000, 39, 0 }, { 0xE525982B, 0x00000000, 39, 0 },
    { 0xE38E38E4, 0x00000000, 39, 0 }, { 0xE1FC780F, 0x00000000, 39, 0 },
    { 0xE070381C, 0xD54339EE, 39, 0 }, { 0xDEE95C4D, 0x00000000, 39, 0 },
    { 0xDD67C8A6, 0xD28B661F, 39, 0 }, { 0xDBEB61EF, 0x00000000, 39, 0 },
    { 0xDA740DA8, 0x00000000, 39, 0 }, { 0xD901B204, 0x00000000, 39, 0 },
    { 0xD79435E5, 0xCD4F851E, 39, 0 }, { 0xD62B80D7, 0x00000000, 39, 0 },
    { 0xD4C77B04, 0x00000000, 39, 0 }, { 0xD3680D37, 0x00000000, 39, 0 },
    { 0xD20D20D2, 0xC8546773, 39, 0 }, { 0xD0B69FCC, 0x00000000, 39, 0 },
    { 0xCF6474A9, 0x00000000, 39, 0 }, { 0xCE168A77, 0xB14E95CC, 39, 0 },
    { 0xCCCCCCCD, 0x00000000, 39, 0 }, { 0xCB8727C1, 0x00000000, 39, 0 },
    { 0xCA4587E7, 0x00000000, 39, 0 }, { 0xC907DA4F, 0x00000000, 39, 0 },
    { 0xC7CE0C7D, 0x00000000, 39, 0 }, { 0xC6980C6A, 0x00000000, 39, 0 },
    { 0xC565C87C, 0x00000000, 39, 0 }, { 0xC4372F86, 0x00000000, 39, 0 },
    { 0xC30C30C3, 0xBABC231B, 39, 0 }, { 0xC1E4BBD6, 0x00000000, 39, 0 },
    { 0xC0C0C0C1, 0x00000000, 39, 0 }, { 0xBFA02FE8, 0xB79E7355, 39, 0 },
    { 0xBE82FA0C, 0x00000000, 39, 0 }, { 0xBD691047, 0xB8E21937, 39, 0 },
    { 0xBC52640C, 0x00000000, 39, 0 }, { 0xBB3EE722, 0x00000000, 39, 0 },
    { 0xBA2E8BA3, 0x00000000, 39, 0 }, { 0xB92143FA, 0x924F6831, 39, 0 },
    { 0xB81702E1, 0x00000000, 39, 0 }, { 0xB70FBB5A, 0xA5917DE9, 39, 0 },
    { 0xB60B60B6, 0xAEDD20C4, 39, 0 }, { 0xB509E68B, 0x00000000, 39, 0 },
    { 0xB40B40B4, 0xAD07B581, 39, 0 }, { 0xB30F6353, 0x00000000, 39, 0 },
    { 0xB21642C9, 0x00000000, 39, 0 }, { 0xB11FD3B8, 0xAA59B97B, 39, 0 },
    { 0xB02C0B03, 0x00000000, 39, 0 }, { 0xAF3ADDC7, 0x00000000, 39, 0 },
    { 0xAE4C415D, 0x00000000, 39, 0 }, { 0xAD602B58, 0xA6E766FE, 39, 0 },
    { 0xAC769184, 0xA6105A53, 39, 0 }, { 0xAB8F69E3, 0x00000000, 39, 0 },
    { 0xAAAAAAAB, 0x00000000, 39, 0 }, { 0xA9C84A48, 0x00000000, 39, 0 },
    { 0xA8E83F57, 0x9A147822, 39, 0 }, { 0xA80A80A8, 0xA1FCBBC9, 39, 0 },
    { 0xA72F053A, 0x00000000, 39, 0 }, { 0xA655C439, 0x899D6569, 39, 0 },
    { 0xA57EB503, 0x00000000, 39, 0 }, { 0xA4A9CF1E, 0x00000000, 39, 0 },
    { 0xA3D70A3E, 0x00000000, 39, 0 }, { 0xA3065E40, 0x00000000, 39, 0 },
    { 0xA237C32B, 0x9492E7F8, 39, 0 }, { 0xA16B312F, 0x00000000, 39, 0 },
    { 0xA0A0A0A1, 0x00000000, 39, 0 }, { 0x9FD809FE, 0x00000000, 39, 0 },
    { 0x9F1165E7, 0x88B2B6BA, 39, 0 }, { 0x9E4CAD24, 0x00000000, 39, 0 },
    { 0x9D89D89E, 0x00000000, 39, 0 }, { 0x9CC8E161, 0x00000000, 39, 0 },
    { 0x9C09C09C, 0x96DFBA90, 39, 0 }, { 0x9B4C6F9F, 0x00000000, 39, 0 },
    { 0x9A90E7D9, 0x63EDACBA, 39, 0 }, { 0x99D722DB, 0x00000000, 39, 0 },
    { 0x991F1A51, 0x64F046A0, 39, 0 }, { 0x9868C80A, 0x00000000, 39, 0 },
    { 0x97B425ED, 0x92D7F561, 39, 0 }, { 0x97012E02, 0x617B421C, 39, 0 },
    { 0x964FDA6C, 0x918C2473, 39, 0 }, { 0x95A02568, 0x90E86F18, 39, 0 },
    { 0x94F2094F, 0x82BBC707, 39, 0 }, { 0x94458094, 0x6CC213BC, 39, 0 },
    { 0x939A85C4, 0x8F05C78A, 39, 0 }, { 0x92F11384, 0x910A6ACE, 39, 0 },
    { 0x92492492, 0x6938A379, 39, 0 }, { 0x91A2B3C5, 0x00000000, 39, 0 },
    { 0x90FDBC09, 0x88BBFEE9, 39, 0 }, { 0x905A3863, 0x6E19513E, 39, 0 },
    { 0x8FB823EE, 0x8B652757, 39, 0 }, { 0x8F1779DA, 0x00000000, 39, 0 },
    { 0x8E78356D, 0x840838CF, 39, 0 }, { 0x8DDA5202, 0x6FDBA647, 39, 0 },
    { 0x8D3DCB09, 0x00000000, 39, 0 }, { 0x8CA29C04, 0x55CF000B, 39, 0 },
    { 0x8C08C08C, 0x87F26399, 39, 0 }, { 0x8B70344A, 0x817481AD, 39, 0 },
    { 0x8AD8F2FC, 0x00000000, 39, 0 }, { 0x8A42F870, 0x5C484869, 39, 0 },
    { 0x89AE408A, 0x00000000, 39, 0 }, { 0x891AC73B, 0x00000000, 39, 0 },
    { 0x88888889, 0x00000000, 39, 0 }, { 0x87F78088, 0x00000000, 39, 0 },
    { 0x8767AB5F, 0x6C1B1206, 39, 0 }, { 0x86D90545, 0x00000000, 39, 0 },
    { 0x864B8A7E, 0x00000000, 39, 0 }, { 0x85BF3761, 0x6EF112D9, 39, 0 },
    { 0x85340853, 0x644C351D, 39, 0 }, { 0x84A9F9C8, 0x8107CD41, 39, 0 },
    { 0x84210842, 0x7C43E63C, 39, 0 }, { 0x83993052, 0x637D2B38, 39, 0 },
    { 0x83126E98, 0x00000000, 39, 0 }, { 0x828CBFBF, 0x00000000, 39, 0 },
    { 0x82082082, 0x7E8DCE43, 39, 0 }, { 0x81848DA9, 0x00000000, 39, 0 },
    { 0x81020408, 0x7986C493, 39, 0 }, { 0x80808081, 0x00000000, 39, 0 },
    { 0x01000000, 0x00000000, 32, 0 }, { 0xFF00FF01, 0x00000000, 40, 0 },
    { 0xFE03F810, 0x00000000, 40, 0 }, { 0xFD08E551, 0x00000000, 40, 0 },
    { 0xFC0FC0FD, 0x00000000, 40, 0 }, { 0xFB188566, 0x00000000, 40, 0 },
    { 0xFA232CF3, 0x00000000, 40, 0 }, { 0xF92FB222, 0x00000000, 40, 0 },
    { 0xF83E0F84, 0x00000000, 40, 0 }, { 0xF74E3FC3, 0x00000000, 40, 0 },
    { 0xF6603D99, 0x00000000, 40, 0 }, { 0xF57403D6, 0x00000000, 40, 0 },
    { 0xF4898D60, 0x00000000, 40, 0 }, { 0xF3A0D52D, 0x00000000, 40, 0 },
    { 0xF2B9D649, 0x00000000, 40, 0 }, { 0xF1D48BCF, 0x00000000, 40, 0 },
    { 0xF0F0F0F1, 0x00000000, 40, 0 }, { 0xF00F00F0, 0xE330853B, 40, 0 },
    { 0xEF2EB720, 0x00000000, 40, 0 }, { 0xEE500EE5, 0xEE500EE5, 40, 0 },
    { 0xED7303B6, 0x00000000, 40, 0 }, { 0xEC979119, 0x00000000, 40, 0 },
    { 0xEBBDB2A6, 0x00000000, 40, 0 }, { 0xEAE56404, 0x00000000, 40, 0 },
    { 0xEA0EA0EA, 0xDDDA4EB3, 40, 0 }, { 0xE9396520, 0x00000000, 40, 0 },
    { 0xE865AC7C, 0x00000000, 40, 0 }, { 0xE79372E3, 0x00000000, 40, 0 },
    { 0xE6C2B449, 0x00000000, 40, 0 }, { 0xE5F36CB0, 0xDA30EB69, 40, 0 },
    { 0xE525982B, 0x00000000, 40, 0 }, { 0xE45932D8, 0x00000000, 40, 0 },
    { 0xE38E38E4, 0x00000000, 40, 0 }, { 0xE2C4A689, 0x00000000, 40, 0 },
    { 0xE1FC780F, 0x00000000, 40, 0 }, { 0xE135A9CA, 0x00000000, 40, 0 },
    { 0xE070381C, 0xD54339EE, 40, 0 }, { 0xDFAC1F75, 0x00000000, 40, 0 },
    { 0xDEE95C4D, 0x00000000, 40, 0 }, { 0xDE27EB2D, 0x00000000, 40, 0 },
    { 0xDD67C8A6, 0xD28B661F, 40, 0 }, { 0xDCA8F159, 0x00000000, 40, 0 },
    { 0xDBEB61EF, 0x00000000, 40, 0 }, { 0xDB2F171E, 0x00000000, 40, 0 },
    { 0xDA740DA8, 0x00000000, 40, 0 }, { 0xD9BA4257, 0x00000000, 40, 0 },
    { 0xD901B204, 0x00000000, 40, 0 }, { 0xD84A598F, 0x00000000, 40, 0 },
    { 0xD79435E5, 0xCD4F851E, 40, 0 }, { 0xD6DF43FD, 0x00000000, 40, 0 },
    { 0xD62B80D7, 0x00000000, 40, 0 }, { 0xD578E97D, 0x00000000, 40, 0 },
    { 0xD4C77B04, 0x00000000, 40, 0 }, { 0xD417328A, 0x00000000, 40, 0 },
    { 0xD3680D37, 0x00000000, 40, 0 }, { 0xD2BA083C, 0x00000000, 40, 0 },
    { 0xD20D20D2, 0xC8546773, 40, 0 }, { 0xD161543E, 0xB0FAD4B7, 40, 0 },
    { 0xD0B69FCC, 0x00000000, 40, 0 }, { 0xD00D00D0, 0xC685FCD0, 40, 0 },
    { 0xCF6474A9, 0x00000000, 40, 0 }, { 0xCEBCF8BC, 0x00000000, 40, 0 },
    { 0xCE168A77, 0xB14E95CC, 40, 0 }, { 0xCD712753, 0x00000000, 40, 0 },
    { 0xCCCCCCCD, 0x00000000, 40, 0 }, { 0xCC29786D, 0x00000000, 40, 0 },
    { 0xCB8727C1, 0x00000000, 40, 0 }, { 0xCAE5D85F, 0xB5ED2BA7, 40, 0 },
    { 0xCA4587E7, 0x00000000, 40, 0 }, { 0xC9A633FD, 0x00000000, 40, 0 },
    { 0xC907DA4F, 0x00000000, 40, 0 }, { 0xC86A7890, 0xBF9C97F0, 40, 0 },
    { 0xC7CE0C7D, 0x00000000, 40, 0 }, { 0xC73293D8, 0x00000000, 40, 0 },
    { 0xC6980C6A, 0x00000000, 40, 0 }, { 0xC5FE7403, 0xB470D0E2, 40, 0 },
    { 0xC565C87C, 0x00000000, 40, 0 }, { 0xC4CE07B0, 0xBC552EF4, 40, 0 },
    { 0xC4372F86, 0x00000000, 40, 0 }, { 0xC3A13DE6, 0xC11AAB3C, 40, 0 },
    { 0xC30C30C3, 0xBABC231B, 40, 0 }, { 0xC2780614, 0x00000000, 40, 0 },
    { 0xC1E4BBD6, 0x00000000, 40, 0 }, { 0xC152500C, 0xB252122F, 40, 0 },
    { 0xC0C0C0C1, 0x00000000, 40, 0 }, { 0xC0300C03, 0xC0300C03, 40, 0 },
    { 0xBFA02FE8, 0xB79E7355, 40, 0 }, { 0xBF112A8B, 0x00000000, 40, 0 },
    { 0xBE82FA0C, 0x00000000, 40, 0 }, { 0xBDF59C92, 0x00000000, 40, 0 },
    { 0xBD691047, 0xB8E21937, 40, 0 }, { 0xBCDD535E, 0x00000000, 40, 0 },
    { 0xBC52640C, 0x00000000, 40, 0 }, { 0xBBC8408D, 0x00000000, 40, 0 },
    { 0xBB3EE722, 0x00000000, 40, 0 }, { 0xBAB65610, 0xB3227A96, 40, 0 },
    { 0xBA2E8BA3, 0x00000000, 40, 0 }, { 0xB9A7862A, 0xAF031970, 40, 0 },
    { 0xB92143FA, 0x924F6831, 40, 0 }, { 0xB89BC36D, 0x00000000, 40, 0 },
    { 0xB81702E1, 0x00000000, 40, 0 }, { 0xB79300B8, 0x00000000, 40, 0 },
    { 0xB70FBB5A, 0xA5917DE9, 40, 0 }, { 0xB68D3134, 0xAD4B5657, 40, 0 },
    { 0xB60B60B6, 0xAEDD20C4, 40, 0 }, { 0xB58A4855, 0xA4D8D637, 40, 0 },
    { 0xB509E68B, 0x00000000, 40, 0 }, { 0xB48A39D4, 0x83B504FE, 40, 0 },
    { 0xB40B40B4, 0xAD07B581, 40, 0 }, { 0xB38CF9B0, 0xAC93E567, 40, 0 },
    { 0xB30F6353, 0x00000000, 40, 0 }, { 0xB2927C2A, 0x00000000, 40, 0 },
    { 0xB21642C9, 0x00000000, 40, 0 }, { 0xB19AB5C5, 0x00000000, 40, 0 },
    { 0xB11FD3B8, 0xAA59B97B, 40, 0 }, { 0xB0A59B42, 0x00000000, 40, 0 },
    { 0xB02C0B03, 0x00000000, 40, 0 }, { 0xAFB321A1, 0x7E2D29EB, 40, 0 },
    { 0xAF3ADDC7, 0x00000000, 40, 0 }, { 0xAEC33E20, 0x00000000, 40, 0 },
    { 0xAE4C415D, 0x00000000, 40, 0 }, { 0xADD5E632, 0x835C737D, 40, 0 },
    { 0xAD602B58, 0xA6E766FE, 40, 0 }, { 0xACEB0F89, 0x99406AC6, 40, 0 },
    { 0xAC769184, 0xA6105A53, 40, 0 }, { 0xAC02B00B, 0x00000000, 40, 0 },
    { 0xAB8F69E3, 0x00000000, 40, 0 }, { 0xAB1CBDD4, 0x00000000, 40, 0 },
    { 0xAAAAAAAB, 0x00000000, 40, 0 }, { 0xAA392F36, 0x00000000, 40, 0 },
    { 0xA9C84A48, 0x00000000, 40, 0 }, { 0xA957FAB5, 0x7FBEBBEA, 40, 0 },
    { 0xA8E83F57, 0x9A147822, 40, 0 }, { 0xA8791709, 0x00000000, 40, 0 },
    { 0xA80A80A8, 0xA1FCBBC9, 40, 0 }, { 0xA79C7B17, 0x00000000, 40, 0 },
    { 0xA72F053A, 0x00000000, 40, 0 }, { 0xA6C21DF7, 0x00000000, 40, 0 },
    { 0xA655C439, 0x899D6569, 40, 0 }, { 0xA5E9F6ED, 0x84B87B30, 40, 0 },
    { 0xA57EB503, 0x00000000, 40, 0 }, { 0xA513FD6C, 0x00000000, 40, 0 },
    { 0xA4A9CF1E, 0x00000000, 40, 0 }, { 0xA4402910, 0x9E7C440F, 40, 0 },
    { 0xA3D70A3E, 0x00000000, 40, 0 }, { 0xA36E71A3, 0x00000000, 40, 0 },
    { 0xA3065E40, 0x00000000, 40, 0 }, { 0xA29ECF16, 0x7D808D12, 40, 0 },
    { 0xA237C32B, 0x9492E7F8, 40, 0 }, { 0xA1D13986, 0x00000000, 40, 0 },
    { 0xA16B312F, 0x00000000, 40, 0 }, { 0xA105A933, 0x00000000, 40, 0 },
    { 0xA0A0A0A1, 0x00000000, 40, 0 }, { 0xA03C1689, 0x00000000, 40, 0 },
    { 0x9FD809FE, 0x00000000, 40, 0 }, { 0x9F747A15, 0x83EE395A, 40, 0 },
    { 0x9F1165E7, 0x88B2B6BA, 40, 0 }, { 0x9EAECC8D, 0x6B9B44DA, 40, 0 },
    { 0x9E4CAD24, 0x00000000, 40, 0 }, { 0x9DEB06C9, 0x8F1B2825, 40, 0 },
    { 0x9D89D89E, 0x00000000, 40, 0 }, { 0x9D2921C4, 0x00000000, 40, 0 },
    { 0x9CC8E161, 0x00000000, 40, 0 }, { 0x9C69169B, 0x7FB3C69D, 40, 0 },
    { 0x9C09C09C, 0x96DFBA90, 40, 0 }, { 0x9BAADE8E, 0x6F55E2DC, 40, 0 },
    { 0x9B4C6F9F, 0x00000000, 40, 0 }, { 0x9AEE72FD, 0x00000000, 40, 0 },
    { 0x9A90E7D9, 0x63EDACBA, 40, 0 }, { 0x9A33CD67, 0x9A33CD67, 40, 0 },
    { 0x99D722DB, 0x00000000, 40, 0 }, { 0x997AE76B, 0x69B92D03, 40, 0 },
    { 0x991F1A51, 0x64F046A0, 40, 0 }, { 0x98C3BAC7, 0x6A2AF5E7, 40, 0 },
    { 0x9868C80A, 0x00000000, 40, 0 }, { 0x980E4156, 0x85C3D1B7, 40, 0 },
    { 0x97B425ED, 0x92D7F561, 40, 0 }, { 0x975A7510, 0x00000000, 40, 0 },
    { 0x97012E02, 0x617B421C, 40, 0 }, { 0x96A8500A, 0x00000000, 40, 0 },
    { 0x964FDA6C, 0x918C2473, 40, 0 }, { 0x95F7CC73, 0x00000000, 40, 0 },
    { 0x95A02568, 0x90E86F18, 40, 0 }, { 0x9548E498, 0x00000000, 40, 0 },
    { 0x94F2094F, 0x82BBC707, 40, 0 }, { 0x949B92DE, 0x00000000, 40, 0 },
    { 0x94458094, 0x6CC213BC, 40, 0 }, { 0x93EFD1C5, 0x8C53F355, 40, 0 },
    { 0x939A85C4, 0x8F05C78A, 40, 0 }, { 0x93459BE7, 0x00000000, 40, 0 },
    { 0x92F11384, 0x910A6ACE, 40, 0 }, { 0x929CEBF5, 0x00000000, 40, 0 },
    { 0x92492492, 0x6938A379, 40, 0 }, { 0x91F5BCB9, 0x00000000, 40, 0 },
    { 0x91A2B3C5, 0x00000000, 40, 0 }, { 0x91500915, 0x91500915, 40, 0 },
    { 0x90FDBC09, 0x88BBFEE9, 40, 0 }, { 0x90ABCC02, 0x6BB5AEAA, 40, 0 },
    { 0x905A3863, 0x6E19513E, 40, 0 }, { 0x90090090, 0x8BB0BBF7, 40, 0 },
    { 0x8FB823EE, 0x8B652757, 40, 0 }, { 0x8F67A1E4, 0x00000000, 40, 0 },
    { 0x8F1779DA, 0x00000000, 40, 0 }, { 0x8EC7AB3A, 0x00000000, 40, 0 },
    { 0x8E78356D, 0x840838CF, 40, 0 }, { 0x8E2917E1, 0x00000000, 40, 0 },
    { 0x8DDA5202, 0x6FDBA647, 40, 0 }, { 0x8D8BE340, 0x00000000, 40, 0 },
    { 0x8D3DCB09, 0x00000000, 40, 0 }, { 0x8CF008CF, 0x8CF008CF, 40, 0 },
    { 0x8CA29C04, 0x55CF000B, 40, 0 }, { 0x8C55841D, 0x00000000, 40, 0 },
    { 0x8C08C08C, 0x87F26399, 40, 0 }, { 0x8BBC50C9, 0x00000000, 40, 0 },
    { 0x8B70344A, 0x817481AD, 40, 0 }, { 0x8B246A88, 0x00000000, 40, 0 },
    { 0x8AD8F2FC, 0x00000000, 40, 0 }, { 0x8A8DCD20, 0x00000000, 40, 0 },
    { 0x8A42F870, 0x5C484869, 40, 0 }, { 0x89F8746A, 0x00000000, 40, 0 },
    { 0x89AE408A, 0x00000000, 40, 0 }, { 0x89645C4F, 0x4F0836C8, 40, 0 },
    { 0x891AC73B, 0x00000000, 40, 0 }, { 0x88D180CD, 0x6A5E536A, 40, 0 },
    { 0x88888889, 0x00000000, 40, 0 }, { 0x883FDDF0, 0x8466044C, 40, 0 },
    { 0x87F78088, 0x00000000, 40, 0 }, { 0x87AF6FD6, 0x00000000, 40, 0 },
    { 0x8767AB5F, 0x6C1B1206, 40, 0 }, { 0x872032AC, 0x7DC57D23, 40, 0 },
    { 0x86D90545, 0x00000000, 40, 0 }, { 0x869222B2, 0x00000000, 40, 0 },
    { 0x864B8A7E, 0x00000000, 40, 0 }, { 0x86053C34, 0x578CE76F, 40, 0 },
    { 0x85BF3761, 0x6EF112D9, 40, 0 }, { 0x85797B91, 0x47E3DB8B, 40, 0 },
    { 0x85340853, 0x644C351D, 40, 0 }, { 0x84EEDD36, 0x00000000, 40, 0 },
    { 0x84A9F9C8, 0x8107CD41, 40, 0 }, { 0x84655D9C, 0x00000000, 40, 0 },
    { 0x84210842, 0x7C43E63C, 40, 0 }, { 0x83DCF94E, 0x00000000, 40, 0 },
    { 0x83993052, 0x637D2B38, 40, 0 }, { 0x8355ACE4, 0x00000000, 40, 0 },
    { 0x83126E98, 0x00000000, 40, 0 }, { 0x82CF7504, 0x00000000, 40, 0 },
    { 0x828CBFBF, 0x00000000, 40, 0 }, { 0x824A4E61, 0x00000000, 40, 0 },
    { 0x82082082, 0x7E8DCE43, 40, 0 }, { 0x81C635BC, 0x792C010D, 40, 0 },
    { 0x81848DA9, 0x00000000, 40, 0 }, { 0x814327E4, 0x00000000, 40, 0 },
    { 0x81020408, 0x7986C493, 40, 0 }, { 0x80C121B3, 0x00000000, 40, 0 },
    { 0x80808081, 0x00000000, 40, 0 }, { 0x80402010, 0x7CE0472D, 40, 0 },
};

#if defined(WIN64) || defined(_WIN64) || defined(_M_X64) || defined(_M_AMD64) \
 || defined(_M_IA64) || defined(__amd64__) || defined(__x86_64__)

static inline
std::uint32_t fast_div_u32(std::uint32_t value, std::uint32_t divisor)
{
    if (divisor < kMaxDivTable) {
        DivRatio32 dt = div_ratio_tbl32_64[divisor];
        std::uint32_t result = (std::uint32_t)(((std::uint64_t)value * dt.mul + dt.add) >> dt.shift);
        return result;
    } else {
        return (value / divisor);
    }
}

#else // !__amd64__

static inline
std::uint32_t fast_div_u32(std::uint32_t value, std::uint32_t divisor)
{
    if (divisor < kMaxDivTable) {
        DivRatio32 dt = div_ratio_tbl32[divisor];
        std::uint32_t result = ((std::uint32_t)(((std::uint64_t)value * dt.mul + dt.add) >> 32u) >> dt.shift);
        return result;
    } else {
        return (value / divisor);
    }
}

#endif // __amd64__

static inline
uint32_t next_random_u32()
{
#if (RAND_MAX == 0x7FFF)
    uint32_t rnd32 = (((uint32_t)rand() & 0x03) << 30) |
                      ((uint32_t)rand() << 15) |
                       (uint32_t)rand();
#else
    uint32_t rnd32 = ((uint32_t)rand() << 16) | (uint32_t)rand();
#endif
    return rnd32;
}

static inline
uint64_t next_random_u64()
{
#if (RAND_MAX == 0x7FFF)
    uint64_t rnd64 = (((uint64_t)rand() & 0x0F) << 60) |
                      ((uint64_t)rand() << 45) |
                      ((uint64_t)rand() << 30) |
                      ((uint64_t)rand() << 15) |
                       (uint64_t)rand();
#else
    uint64_t rnd64 = ((uint64_t)rand() << 32) | (uint64_t)rand();
#endif
    return rnd64;
}

void compile_time_div_test()
{
    unsigned int num = rand();
    unsigned int rnd = rand();
    printf("num = %d", num / 7);
    printf("num = %d", num / 5);
    bool carry = (rnd > 16368) ? 1 : 0;
    num += carry;
    printf("num = %d", num);
}

void uint128_test()
{
    std::uint64_t rnd_low = next_random_u64():
    std::uint64_t rnd_high = next_random_u64();
    std::uint64_t divisor = ((std::uint64_t)rand() << 32) | rand() + 1;

    __uint128_t rnd128 = ((__uint128_t)rnd_high << 64) | rnd_low;
    __uint128_t divisor128 = divisor;
    __uint128_t p = rnd128 / divisor128;
    printf("%llu / %llu = %llu, ", (std::uint64_t)rnd128, (std::uint64_t)divisor128, (std::uint64_t)p);
}

int main(int argc, char * argv[])
{
    srand((unsigned)time(NULL));

    std::uint32_t rnd = rand();
    std::uint32_t divisor = rand();

    auto p = fast_div_u32(rnd, divisor);
    printf("%u / %u = %u, ", rnd, divisor, p);

    uint128_test();

    return 0;
}
